package dp.备忘录dfs;

import java.util.Arrays;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 组合总和377.java
 * @createTime 2024年03月29日 17:29:00
 */
public class 组合总和377 {
	// 记忆化数组，用于存储已经计算过的结果
	private int[] memo;

	public int combinationSum4(int[] nums, int target) {
		memo = new int[target + 1];
		Arrays.sort(nums);
		// 初始化记忆化数组中的所有值为-1，表示这些值尚未被计算
		Arrays.fill(memo, -1);
		// 目标为0的组合数为1，即不取任何数字
		memo[0] = 1;
		// 调用递归函数开始计算
		return dfs(nums, target);
	}

	private int dfs(int[] nums, int target) {
		// 如果目标小于0，说明这条路径不可行，返回0
		if (target < 0) {
			return 0;
		}
		// 如果这个目标已经被计算过，直接返回结果
		if (memo[target] != -1) {
			return memo[target];
		}
		// 初始化当前目标的组合数为0
		int count = 0;
		// 遍历每个数字，尝试所有可能的选择
		for (int num : nums) {
			// 每选一个数，目标值减少
			count += dfs(nums, target - num);
		}
		// 计算完成后，将结果存储在memo数组中，避免重复计算
		memo[target] = count;
		// 返回计算的结果
		return count;
	}
}
